Min_25 筛

不会真的有人在考了 n\sout{n} 次后还不会一个算法吧 不会吧不会吧

老早就学了这玩意,但是几次考试板子也写不对。于是近期重新梳理了一下算法。


算法流程

阅读全文 »

[CERC2017] Gambling Guide

Description

给定一张 nn 个点 mm 条边的无向图。当你在点 uu 时,你可以花费 11 的费用向系统询问当前可以去哪个点,系统会从点 uu 的所有出边中随机选择一条告诉你。你可以选择去,或者重新花费并询问。初始时刻你在 11 号点,要去 nn 号点。求最少花费的期望。
1n,m3×1051\leq n,m\leq 3\times 10^5

Solution

阅读全文 »

Fibonacci's Magic

Fibonacci\rm Fibonacci 数列的性质很多,有的常考,有的不常考。
这些性质都有可能是解题关键。这里稍作总结。
Fibonacci\rm Fibonacci 的定义很多,本文采取如下的递归定义:

fi={0                         i=01                         i=1fi1+fi2          i2f_i=\begin{cases}

阅读全文 »

AGC002F Leftmost Ball

Description

给你 nn 种颜色的球,每个球有 kk 个,把这 n×kn\times k 个球排成一排,把每一种颜色的最左边出现的球涂成白色(初始球不包含白色),求最终有多少种不同的颜色序列,答案对 109+710^9+7 取模。
1n,k2×1031\leq n,k\leq 2\times 10^3

Solution

阅读全文 »

容斥原理

看了 lsqs\sout{\rm{lsqs}} 的博客才知道自己容斥原理学的不够深
容斥大概是计数中非常重要的了。以前都是式子直接用,核心的层次大抵是没有接触到,证明的过程也很少看。所以总结一些比较基础的知识和证明过程。以后式子用起来希望能更有底气。🙏


原始公式

阅读全文 »

Comet OJ Contest 11 F arewell

Description

给定一张 nn 个点 mm 条边的图,一条边 (u,v)(u,v)13\frac{1}{3} 的概率消失,13\frac{1}{3} 的概率定向成 uvu\rightarrow v13\frac{1}{3} 的概率定向成 vuv\rightarrow u 。求最后的图是 DAG\rm{DAG} 的概率。

n20,mn(n1)2n\leq 20,m\leq \frac{n(n-1)}{2}

Solution

阅读全文 »